Auflistung nach Schlagwort "descriptive complexity"

Auflistung nach Schlagwort "descriptive complexity"

Sortiert nach: Sortierung: Ergebnisse:

  • Counting and enumerating in first-order team logics 
    Müller, Fabian (Hannover : Institutionelles Repositorium der Leibniz Universität Hannover, 2024)
    Descriptive complexity theory is the study of the expressibility of computational problems in certain logics. Most of the results in this field use (fragments or extensions of) first-order logic or second-order logic to ...
  • Descriptive complexity of circuit-based counting classes 
    Haak, Anselm (Hannover : Institutionelles Repositorium der Leibniz Universität Hannover, 2021)
    In this thesis, we study the descriptive complexity of counting classes based on Boolean circuits. In descriptive complexity, the complexity of problems is studied in terms of logics required to describe them. The focus ...
  • A fragment of dependence logic capturing polynomial time 
    Ebbing, Johannes; Kontinen, Juha; Mueller, Julian-Steffen; Vollmer, Heribert (Braunschweig : Tech. Univ. Braunschweig, 2014)
    In this paper we study the expressive power of Horn-formulae in dependence logic and show that they can express NP-complete problems. Therefore we define an even smaller fragment D*-Horn and show that over finite successor ...
  • On second-order monadic monoidal and groupoidal quantifiers 
    Kontinen, Juha; Vollmer, Heribert (Braunschweig : Tech. Univ. Braunschweig, 2010)
    We study logics defined in terms of second-order monadic monoidal and groupoidal quantifiers. These are generalized quantifiers defined by monoid and groupoid word-problems, equivalently, by regular and context-free ...
  • Parameterized complexity of weighted team definability 
    Kontinen, Juha; Mahmood, Yasir; Meier, Arne; Vollmer, Heribert (Cambridge : Cambridge Univ. Press, 2024)
    In this article, we study the complexity of weighted team definability for logics with team semantics. This problem is a natural analog of one of the most studied problems in parameterized complexity, the notion of weighted ...